The image, especially multivalued image, contains a very large amount of information, and has a problem that the volume of data becomes enormous when the image is accumulated and transmitted. Therefore, in the accumulation and transmission of the image, a high efficiency coding is employed to reduce the volume of data by removing the redundancy of image, or changing the contents of the image to such an extent that the degradation of image quality is visually unrecognizable.
For example, in a JPEG method recommended by ISO and ITU-T as the international standard coding method for still image, the image data is converted into DCT coefficients by making the discrete cosine transform (DCT) for every block (8 pixels×8 pixels), each coefficient being quantized, and compressed by making the entropy coding. As the compression techniques using this DCT, H261 and MPEG1/2/4 are provided, besides JPEG.
The Hadamard transform is well known as a partial processing of this DCT conversion, or a processing of transforming the image data. The Hadamard transform is the simplest orthogonal transform implemented only by addition and subtraction in which the elements of a transform matrix consist of 1 or −1. In the following, the Hadamard transform will be simply described below.
The transform matrix H2 of 2-point Hadamard transform is defined as follows.
      [          Formula      ⁢                          ⁢      1        ]                                                                ⁢                                    H              2                        =                                          1                                  2                                            ⁡                              [                                                                            1                                                              1                                                                                                  1                                                                                      -                        1                                                                                            ]                                                                          (          1          )                    
A general N(=2n)-point Hadamard transform matrix HN is defined recursively by the Kronecker product between an N/2-point Hadamard transform matrix HN/2 and the 2-point Hadamard transform matrix H2 as follows.
      [          Formula      ⁢                          ⁢      2        ]                                                                                                                            ⁢                                                      H                    N                                    =                                                            H                                              N                        /                        2                                                              ⊗                                          H                      2                                                                                                                                              =                                                      1                                          2                                                        ⁡                                      [                                                                                                                        H                                                          N                              /                              2                                                                                                                                                            H                                                          N                              /                              2                                                                                                                                                                                                        H                                                          N                              /                              2                                                                                                                                                            -                                                          H                                                              N                                /                                2                                                                                                                                                                          ]                                                                                                            (          2          )                    
From the above definition, a 4-point Hadamard transform matrix is obtained as
      [          Formula      ⁢                          ⁢      3        ]                                                                ⁢                                    H              4                        =                                          1                2                            ⁡                              [                                                                            1                                                              1                                                              1                                                              1                                                                                                  1                                                                                      -                        1                                                                                    1                                                                                      -                        1                                                                                                                        1                                                              1                                                                                      -                        1                                                                                                            -                        1                                                                                                                        1                                                                                      -                        1                                                                                                            -                        1                                                                                    1                                                                      ]                                                                          (          3          )                    
This transform matrix is called a natural type, in which the basis vectors are not arranged in the sequency order. The sequqency is similar to frequency. If the basis vector in the second row is moved to the fourth row by repeating the substitution of basis vectors, the transform matrix WH4 is generated in which the basis vectors are arranged in the sequency order.
      [          Formula      ⁢                          ⁢      4        ]                                                                ⁢                                    WH              4                        =                                          1                2                            ⁡                              [                                                                            1                                                              1                                                              1                                                              1                                                                                                  1                                                              1                                                                                      -                        1                                                                                                            -                        1                                                                                                                        1                                                                                      -                        1                                                                                                            -                        1                                                                                    1                                                                                                  1                                                                                      -                        1                                                                                    1                                                                                      -                        1                                                                                            ]                                                                          (          4          )                    
The above transform matrix is called a Walsh type or Walsh Hadamard transform matrix. The Hadamard transform is known as a reversible orthogonal transform, in which both the natural type and the Walsh type are capable of reversible transform, and the transform matrix is symmetric.
Moreover, if the Kronecker product is applied twice to the 4-point Hadamard transform matrix, a 16-point Hadamard transform matrix H16 is obtained, as shown below. FIG. 1 shows the details of the transform matrix H16.
      [          Formula      ⁢                          ⁢      5        ]                                                                ⁢                                                                                          H                    16                                    =                                                            H                      4                                        ⊗                                          H                      2                                        ⊗                                          H                      2                                                                                                                                            =                                                            1                      2                                        ⁡                                          [                                                                                                                                  H                              4                                                                                                                                          H                              4                                                                                                                                          H                              4                                                                                                                                          H                              4                                                                                                                                                                                          H                              4                                                                                                                                          -                                                              H                                4                                                                                                                                                                        H                              4                                                                                                                                          -                                                              H                                4                                                                                                                                                                                                                        H                              4                                                                                                                                          H                              4                                                                                                                                          -                                                              H                                4                                                                                                                                                                        -                                                              H                                4                                                                                                                                                                                                                        H                              4                                                                                                                                          -                                                              H                                4                                                                                                                                                                        -                                                              H                                4                                                                                                                                                                        H                              4                                                                                                                          ]                                                                                                                                (          5          )                    
It is generally said that the Hadamard transform is the reversible transform, but this means that the Hadamard transform is mathematically reversible. That is, it is premised that there is no operation error in the transform and the reverse transform. On the other hand, a transform that keeps the transform coefficients reversible by rounding to the whole number will be called a lossless transform, for distinction from the mathematically reversible transform hereafter in this specification
When the data below the decimal point of the Hadamard transform coefficients is rounded to the whole number, the data after reverse transform may not be restored to the original data by simply truncate or rounding off. This is because the bit information below the decimal point is lost.
In Tadayoshi Nakayama, Hideshi Osawa, Naoto Kawamura, “New lossless transform and application to lossless two-dimensional DCT”, Gadenshi, Vol. 31, No. 5, pp. 787-793, September 2002 (document 1), the lossless transform is implemented by performing a characteristic rounding process for the 4-point Hadamard transform. However, no rounding process for acquiring the reversible transform coefficients in the 16-point Hadamard transform was proposed.
In the document 1, there was described a method for extending the 4-point lossless Hadamard transform to the 16-point lossless Hadamard transform or the two-dimensional 4×4-point lossless Hadamard transform, in which the existent 4-point lossless Hadamard transforms are cascade connected, and processed at two stages, but the 16-point lossless Hadamard transform is not directly operated. The 16-point lossless Hadamard transform coefficients obtained by the cascade connection process or the two-dimensional 4×4-point lossless Hadamard transform coefficients has the rounding errors of two rounding processes convoluted. Since the rounding process for the lossless transform is a non-linear operation, the convoluted rounding error has non-linearity, and is less favorable for the transform coefficients. That is, if the rounding errors of two rounding processes are convoluted, a lot of non-linear rounding errors are convoluted, resulting in a problem.
Also, since it is required that the rounding process is performed twice for each transform coefficient, there is a problem that the operation amount increases.